package com.dh.leetcode.four;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * @ClassName: _475_heaters
 * @Description: 475. 供暖器
 * 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
 * <p>
 * 在加热器的加热半径范围内的每个房屋都可以获得供暖。
 * <p>
 * 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
 * <p>
 * 说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
 * <p>
 * 示例 1:
 * <p>
 * 输入: houses = [1,2,3], heaters = [2]
 * 输出: 1
 * 解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
 * 示例 2:
 * <p>
 * 输入: houses = [1,2,3,4], heaters = [1,4]
 * 输出: 1
 * 解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
 * 示例 3：
 * <p>
 * 输入：houses = [1,5], heaters = [2]
 * 输出：3
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/heaters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: shouzimu
 * @Date: 2021/12/20 11:03
 */
public class _475_heaters {

    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int max = 0;
        for (int house : houses) {
            int rightIndex = binarySearchGreater(heaters, house);
            int leftIndex = binarySearchLess(heaters, house);
            if (rightIndex < 0) {
                rightIndex = leftIndex;
            }
            if (leftIndex < 0) {
                leftIndex = rightIndex;
            }
            int len = Math.abs(heaters[rightIndex] - house);
            int left = Math.abs(heaters[leftIndex] - house);
            if (len > left) {
                len = left;
            }
            if (len > max) {
                max = len;
            }
        }
        return max;
    }

    private int binarySearchGreater(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int mid;
        while (l <= r) {
            mid = l + ((r - l) >> 1);
            if (nums[mid] >= target) {
                if (mid == 0 || nums[mid - 1] < target) {
                    return mid;
                } else {
                    r = mid - 1;
                }
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    private int binarySearchLess(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int mid;
        while (l <= r) {
            mid = l + ((r - l) >> 1);
            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                if ((mid == nums.length - 1) || (nums[mid + 1] > target)) {
                    return mid;
                } else {
                    l = mid + 1;
                }
            }
        }
        return -1;
    }

    @Test
    public void findRadiusTest() {
//         Assert.assertEquals(161834419, findRadius(new int[]{282475249, 622650073, 984943658, 144108930, 470211272, 101027544, 457850878, 458777923}, new int[]{823564440, 115438165, 784484492, 74243042, 114807987, 137522503, 441282327, 16531729, 823378840, 143542612}));
        Assert.assertEquals(498, findRadius(new int[]{1, 1, 1, 1, 1, 1, 999, 999, 999, 999, 999}, new int[]{499, 500, 501}));
        Assert.assertEquals(13, findRadius(new int[]{1, 2, 3, 5, 15}, new int[]{2, 30}));
        Assert.assertEquals(1, findRadius(new int[]{1, 2, 3}, new int[]{2}));
        Assert.assertEquals(1, findRadius(new int[]{1, 2, 3, 4}, new int[]{1, 4}));
        Assert.assertEquals(3, findRadius(new int[]{1, 5}, new int[]{2}));
    }
}
